#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-07-13 9:40 上午
# @Author  : yangdy
# @File    : 2020-07-13.350. 两个数组的交集 II
# @Software: PyCharmCE
from typing import List


class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans = []
        # o(n*m) 枚举  192ms
        # l1 = len(nums1)
        # l2 = len(nums2)
        # for i in range(l1):
        #     for j in range(l2):
        #         if nums1[i] == nums2[j]:
        #             ans.append(nums1[i])
        #             nums2[j] = None
        #             break
        #
        # o(max(nlogn,mlogm)) 排序后双指针 80ms
        # l1, l2 = len(nums1), len(nums2)
        # nums1.sort()
        # nums2.sort()
        # i, j = 0, 0
        # while i < l1 and j < l2:
        #     x, y = nums1[i], nums2[j]
        #     if x == y:
        #         ans.append(x)
        #         i, j = i+1, j+1
        #     elif x < y:
        #         i += 1
        #     else:
        #         j += 1
        # o(max(cn, m)) 使用map hash 64ms
        l1, l2 = len(nums1), len(nums2)
        m1 = {}
        for i in range(l1):
            if m1.get(nums1[i]):
                m1[nums1[i]] += 1
            else:
                m1[nums1[i]] = 1
        for i in range(l2):
            if m1.get(nums2[i]):
                m1[nums2[i]] -= 1
                ans.append(nums2[i])

        return ans


solve = Solution()

questions = [
    ([1, 2, 2, 1], [2, 2]),
    ([4, 9, 5], [9, 4, 9, 8, 4]),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    print('ans:', solve.intersect(q[0], q[1]))
